package problem239_Sliding_Window_Maximum;

import java.util.LinkedList;

public class Solution {
	 public int[] maxSlidingWindow(int[] nums, int k) {
		 if(nums==null||nums.length==0)
		        return new int[0];
		 LinkedList<Integer> dequeue=new LinkedList<>();
		 int[] result=new int[nums.length-k+1];
		 for(int i=0;i<nums.length;i++){
			 if(!dequeue.isEmpty()&&dequeue.peekFirst()+k==i){
				 dequeue.poll();
			 }
			 while(!dequeue.isEmpty()&&nums[dequeue.peekLast()]<nums[i]){
				 dequeue.pollLast();
			 }
			 dequeue.offer(i);
			 if(i+1-k>=0){
				 result[i+1-k]=nums[dequeue.peekFirst()];
			 }
		 }
		 return result;
	 }
}
